Prime Numbers: How One Alteryx Weekly Challenge Led Me Down a Rabbit Hole

Why do people like prime numbers?

Prime numbers are intuitive enough for anyone to access (integers only divisible by 1 and itself), yet they tickle the imagination by going off to infinity without any pattern. Christopher, the main character in the novel “The Curious Incident of the Dog in the Night-Time” by Mark Haddon, describes “Prime numbers are what is left when you have taken all the patterns away. I think prime numbers are like life. They are very logical but you could never work out the rules, even if you spent all your time thinking about them.” On a practical note, primes are very useful in cryptography (RSA encryption).

Defining the Problem

Alteryx weekly challenge #79: “Find the closest prime number” first caught my interest, then stumped me as I realized I didn’t know where to start. A conversation with a friendly mathematician led to further questions and ideas, and as  it turns out, I quite like primes, so this ended up leading me down a number of enjoyably time-consuming rabbit holes.

But before we get there, the conversation reminded me that I knew the concept of ‘modulo’ and the fact that this function is supported by Alteryx’s formula tool. Modulo gives the integer that is ‘left over’ when your number, call it n, is divided by another integer, say t. Modulo 0 means that n is perfectly divisible by t with nothing left over. This is ideal for finding primes, as a prime number will have only two numbers with modulo 0: 1 and itself.

I set about building my workflow and attempting 4 separate but related challenges (‘sub-challenges’/rabbit holes):

1. List all divisors of n.
2. List all primes up to n (prime number generator).
3. Find the nearest prime to n without a lookup table. (This is the original weekly challenge #79.)
4. Find the nearest prime to n using a lookup table.

Play along: Feel free to attempt these sub-challenges on your own before reading further in order to compare answers in the comments!

1. List all divisors of n.

This generates a handy list of integers by which n is divisible (divisors).

I first generated a list of integers from 1 to n, as I needed to test each of them to see if they were divisible by n. I then used the modulo function in the formula tool to show me the modulo for each integer and filtered out the ones with modulo not equal to 0. I then output the list of divisors.

Prime numbers have two divisors with modulo 0, and any integer with more than 2 such divisors is called a composite number. The divisors of a composite number are all themselves prime, or can be sub-divided into prime numbers.

2. List all primes up to n (prime number generator).

This workflow was quite neat, it generates a list of all prime numbers up to n. For this, I built a prime-number-generator iterative macro.

It had to be an iterative macro as the method I used to check if a number was prime was based upon the workflow from challenge 1 above. After checking all the divisors for modulo 0, I then counted the number of such divisors. If the count was greater than 2, the number was not prime. I could have changed the logic to “does not equal 2” but then I would have to remember to only look for a count of 1, as that would exclude the divisor 1, which is unique among primes for only being divisible by one number (itself).

This workflow would have only checked if one number at a time was prime. In order to look for all numbers up to n, I had to generate rows 1 to n and have the iterative macro check each number (t) until I reached n. In order for it to know when to stop iterating, I included a filter within the macro to check if t < n.

In this solution, I appended a column to show the count of all primes up to n. It just repeats the value down the entire column, but I liked being able to see the count at a glance.

And inside the guts of the macro:

3. Find the nearest prime to n (without a lookup table).

This was the original weekly challenge #79.

I used the same prime number generator macro as a base, but with a few tweaks. The original macro starts from 1 and lists all prime numbers up to n. I wanted to start from n and simultaneously look for the first prime number larger than, and the first prime number smaller than, n.

So I ran the two macros in parallel coming from the input, the first starting at n and adding 1 until a prime was found, while the second one did the same, but subtracting 1 with each iteration. I then unioned the two outputs and appended the original n.

From there, it was a case of finding the differences between the primes and n, and then testing which of the two (if either) had the smallest difference. The output contained n, the nearest prime(s), and the difference. I also included a Unique tool before the end for tidiness, since if n is prime, the workflow outputs the same record twice.

And inside the nearest-prime-higher macro (the only difference with the nearest-prime-lower macro is that the second formula tool calculates [n]=[n]-1 instead of +1:

After reviewing some of the other answers on the Alteryx Community page for this challenge, I found my Data School classmate Natasha had posted one solution that would have made this workflow (as well as those of the other sub-challenges) more efficient: rather than testing from 1 to n, she only tested odd values from 1 to n for primeness.

4. Find the nearest prime to n using a lookup table.

The mathematician suggested a learning model where the lookup table is added to each time an n larger than any previously-tested n is tested. I.e. it would be more efficient in that rather than having to generate primes each time, it would do the simpler function of first only checking n against a lookup table. Only if n were larger than anything in the lookup table, would it start generating primes starting from the largest value of the lookup table and working up until it found one larger than n. These new values would then be unioned to the table for future tests.

This was the most time-consuming challenge and even attempting to write it up has so far already given me more ideas to play with, so I will return to this in a future blog post! Stay tuned, and in the meantime, let me know if you attempted the sub-challenges differently in the comments below.